﻿#include <vector>
#include <iostream>
//#include <list>

using namespace std;
typedef unsigned uint;

class graf //klasa bazowa grafow 
{
protected:
    uint v,e;
public:
    uint getv(){return v;};
    uint gete(){return e;};
    void show(); 
    void addv();
    void delv();
    void adde();
    void dele();
    void fillrand();
	uint kruskal();
	uint prim();
    uint counte();
	//graf():v(0),e(0){};
	//graf(uint vv,uint ee):v(vv),e(ee){};
	//graf(uint vv):v(vv),e(0){};
	graf(uint vv=0,uint ee=0):v(vv),e(ee){};

	~graf(){};
};

class grafm: public graf//macierz wag
{
	//zrobić implementacje nieskierowany spójny, łatwiej i tak wszystko na tym polega
private:
	bool skierowany;
	vector <vector<unsigned>> mac;
public:
	bool czySkierowany(){return skierowany;};
    void adde(unsigned x,unsigned y,unsigned waga=1);//bardziej set, nie add
    void addv(unsigned iledodac=1);
    void delv();
    void delv(unsigned x);
    void dele(unsigned x,unsigned y,bool all=false);//odejmuje 1 wage
    void show();
    void fillrand();
    void make_sym();
    unsigned counte();
	void loadsample();
	void loadsample1();
	uint kruskal();
	uint prim(int start=2);

    grafm():graf(0,0),skierowany(false){}; //konstruktor bezparametrowy
    grafm(grafm &old_grafm);//copy
	grafm(uint vv);

	~grafm(){};  
};

class kraw
{
public:
	uint vz;
	uint vdo;
	uint waga;
	friend ostream & operator<< (ostream &wyjscie,const kraw &k);
	kraw(uint x,uint y,uint z):vz(x),vdo(y),waga(z){};
	kraw(){};
};

class grafl : public graf //lista krawiedzi
{
private:
	  vector <kraw> mac;
public:  

	int FindMinWagaZ(uint v,uint &dokad);
	void adde(uint v,uint vv,uint waga);
	void dele(uint v,uint vv);
	void show();
	uint getv();
	uint counte();
	uint countv();
	void fillrand();	
	void loadsample();
	void loadsampleD();
	int djikstra(uint Z,uint DO);
	int getw(uint Z,uint DO);
	int bell(uint Z);

	uint kruskal();
	uint prim(int start=2);

	grafl(grafl &old_grafl);
	grafl(uint ilekrawedzi=7);

	~grafl(){};
};
class node
{
public:
	uint wierzcholek;//vdo
	uint waga;
	bool operator==(const node &q) {return wierzcholek==q.wierzcholek;};
	node(uint vdo,uint wage):wierzcholek(vdo),waga(wage){};
};

class grafs:public graf // lista sasiadow, nie moze byc wolny wierzcholek, musi byc polaczony w tej implementacji
{
private:
		vector <vector<node>> lista;//macierz juz bardziej ale moze kiedys
public:
	int FindMinWagaZ(uint v,uint &dokad);
	void adde(uint vz,uint vdo,uint waga);//do ktorego dodac krawedz vz=wierzcholek z ktorego lecim
	void dele(uint vz,uint vdo);//usuwa na głupa, poprawić!
	int getw(uint vz,uint vdo);
	uint counte();
	void show();
	void loadsampleD();
	void loadsample();
	int djikstra(uint Z,uint DO);
	int bell(uint Z);

	uint kruskal();
	uint prim();
	vector<node> & operator[](size_t el) {return lista[el];}

	grafs(uint ilev=6,bool full=true);//false=pusty
	grafs(grafs &old_graf);

};
class element
{
public:
	uint vdo;
	uint waga;
	element* next;
	element(uint Vdo=0,uint Waga=1):vdo(Vdo),waga(Waga){next=NULL;};
	void show()
	{
		cout<<"["<<vdo<<"]"<<"\t"<<waga<<" ->  ";
	}
};

class lista
{
private:
	element* first;
	element* last;
	uint ilosc;
public:
	lista():first(NULL),last(NULL),ilosc(0){};
	~lista();//usunac wszyskie wskazniki

	element* push_back(uint Vdo,uint Waga=1);//dodaj krawedz
	void del(uint ktory);//ktory=krawedz do ktorego V
	element* index(uint n);
	uint getsize(){return ilosc;}
	void show();
	uint getw(uint ktory);
	element* search(uint vdo);//zwraca wskaznik na poprzedni element!!
}; 

class grafp : public graf
{
	//od razu nieskierowany,i spojny
private:
	vector <lista> tab;
public:
	
	void addv();//dodaje kolejny wierzcholek(kolejna lista)
	void delv(uint ktory=0);//usuwa ostatni wierzcholek i wszystkie polaczenia z niego wychodzace
	void adde(uint vz,uint vdo, uint waga);//do tab[vz].lista dodać 
	void dele(uint vz,uint vdo);
	uint getw(uint vz,uint vdo);
	void show();
	grafp(uint ilev);//tworzy rand graf o V=ilev;
	lista & operator[](size_t el) {return tab[el];}
};

struct E
{
	int wart_drogi;
	int nr_wezla;//do którego idziemy
	int poprzednik;//poprzednik w grafie(z którego)
};



// 0=brak krawêdzi, niedopuszczamy ujemnych wag
// do it czytając z czegokolwiek
//
/*Dijkstra pseudoalgorytm
wagi nieujemne must be
można w tab 2-wym,wtedy kazdy krok widac i debugowanie easy
trzeba zapisac z którego V dana droga
w 1 kroku mogą być ciągle nieskończonośći-nie ma bezpośredniej drogi
jak jest droga ustalona na danym etapie to pozniej olewamy dany V

końcową droge wyznaczmy dzięki poprzednikom
przy okazji wyznaczmi po kolei najkrótsze drogi do danych wierzhołków

class elementD
{
uint droga;//droga w danej komórce
uint zV;//z którego wierzchołka
bool ustalony;//true=ustalony, nie rozpatrujemy
};
while(lista pełna)
{}
//propozycja:

struct E
{
	int wart_drogi;
	int nr_wezla;//do którego idziemy
	int poprzednik;//poprzednik w grafie(z którego)
	E* next;//next element 
}

E* list=new E[n];//n=ileV 
E* found=new E[n];//znalezione najkrotsze drogi aka ustalone

pseudokod
wybierz V;

make lista min połączeń;
	z tych, ktore rozpatrujemy;
find min;
move from list to found;

licz cala droga;

*/
